package com.cuz.for2024;

import java.lang.reflect.Array;
import java.util.Arrays;

public class T516 {


    public static void main(String[] args) {
        System.out.println(new T516().longestPalindromeSubseq("bbbab"));
        System.out.println(new T516().longestPalindromeSubseq2("bbbab"));
    }

    public int longestPalindromeSubseq2(String s) {
        int length = s.length();
        int[][] dp = new int[length][length];
        for (int i = 0; i < length; i++) {
            dp[i][i] = 1;
        }
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i+1; j < length; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][length - 1];
    }

    private void print(int[][]dp){
        System.out.println("===");
        for (int[] ints : dp) {
            System.out.println(Arrays.toString(ints));
        }
        System.out.println("===");
    }

    public int longestPalindromeSubseq(String s) {
        return process(s, 0, s.length() - 1);
    }


    private int process(String s, int i, int j) {
        if (i < 0 || j < 0 || i >= s.length() || j >= s.length()) {
            return 0;
        }
        if (j < i) {
            return 0;
        }
        if (j == i) {
            return 1;
        }
        if (s.charAt(i) == s.charAt(j)) {
            return process(s, i + 1, j - 1) + 2;
        }
        return Math.max(process(s, i + 1, j), process(s, i, j - 1));
    }
}
